package com.Jancode.leetcode;

import java.util.List;
import com.Jancode.leetcode.util.TreeNode;
import java.util.LinkedList;
import java.util.Deque;

public class BTInorderTraversal {

    class Solution {
        // the container to store the result set
        private List<Integer> inorder = new LinkedList<>();
        public List<Integer> inorderTraversal(TreeNode root) {
            traverse(root);
            return inorder;
        }

        // traverse the subtree with the root node 
        // specified by the first argument in according to the inorder 
        private void traverse(TreeNode root) { 
            /*
             * Implementation notes:
             * 
             *           parent     // has been traversed
             *             |
             *            root      // This method now is used to deal with the root.
             *           /    \     //  Every recursive call, make the method down. 
             *        right  left   
             *        /    \ /   \
             *       ...   ...   ...
             */
            if(root == null) return;

            // First deal with the left subtree of root
            traverse(root.left);
            // Then followed by the root node
            inorder.add(root.val);
            // Finally deal with the right subtree of root
            traverse(root.right);
        }

        // We use the iterating method to faster traversal speed.
        private void traverseFaster(TreeNode root) {
            // This stack is used to the record the root of current node
            Deque<TreeNode> stack = new LinkedList<>();

            // the current node where we start to solve this 
            // subtree similar problem - inorder traversal 
            TreeNode curr = root;
            while(curr != null || !stack.isEmpty()) {
                // First deal with the left subtree of curr
                while(curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                }
                // Now curr is null, we can fetch the current node - the parent from the top
                // of the stack we set. Then we start to deal with the node.
                curr = stack.pop();
                inorder.add(curr.val);
                // Final we should process the right subtree of this current node now.
                curr = curr.right;
            }
        }
    }
}
